This subproject is one of many research subprojects utilizing the resources provided by a Center grant funded by NIH/NCRR. Primary support for the subproject and the subproject's principal investigator may have been provided by other sources, including other NIH sources. The Total Cost listed for the subproject likely represents the estimated amount of Center infrastructure utilized by the subproject, not direct funding provided by the NCRR grant to the subproject or subproject staff. The de novo design of protein-protein interfaces is a stringent test of our understanding of the principles underlying protein-protein interactions and would enable unique approaches to biological and medical challenges. Here we describe a motif-based method to computationally design protein-protein complexes with native-like interface composition and interaction density. Using this method we designed a pair of proteins, Prb and Pdar, that heterodimerize with a Kd of 130 nM, 1000-fold tighter than any previously designed de novo protein-protein complex. Directed evolution identified two point mutations that improve affinity to 180 pM. Crystal structures of an affinity-matured complex reveal binding is entirely through the designed interface residues. Surprisingly, in the in vitro evolved complex one of the partners is rotated 180 degrees relative to the original design model, yet still maintains the central computationally designed hotspot interaction and preserves the character of many peripheral interactions. This work demonstrates that high-affinity protein interfaces can be created by designing complementary interaction surfaces on two noninteracting partners and underscores remaining challenges.